This notebook describes implementation of the Boruta permutations method to identify consensus features from the TARGET pediatric AMl dataset.

Methods

We applied Boruta as implemented in the Boruta R package (v.6.0.0). We implemented the Boruta permuataions method with a consensus rank importance metric, and conducted bootstraps of data subset selection (2/3rds of data, to simulate iteratively redraw of training sample subset). Each Boruta iteration was allowed to run for up to 100 steps, over which the algorithm designated “confirmed”, “tentative”, and “rejected” features.

Hyperparameter sets used for algorithm with Boruta permuatations were informed by preliminary investigation of model performances across hyperparameter sets for each algorithm. The initial defined training and test data subsets, as used to measure differential gene expression, were used in hyperparameter optimization and to derive the rank-based consensus importance measure as described below.

Consensus Importance (‘nrank’)

To calculate a consensus importance metric, we define a method to take the median normalized absolute rank of features from across 4 algorithms (lasso, XGBoost, Random Forest, and SVM).

Steps to calculate this normalized median importance include:

  1. Calculate algorithm-specific importances.
  2. Take absolute importances from (1).
  3. Calculate naive rank (index-based) of importances from (2).
  4. Calcualte normalized rank from (3).
  5. Calculate median normalized rank and return.

We settled on this strategy due to properties of Boruta and feature selection. For comparison, a standard of Boruta using Random Forest importance shows oscillation of shadow feature importances, gradual exclusion of rejected features, and retention of important features (Figure 1)

History of shadow feature importances over permuatations in a single Boruta iteration using Random Forest importance (green: confirmed features, red: rejected features, yellow: tentative features).

History of shadow feature importances over permuatations in a single Boruta iteration using Random Forest importance (green: confirmed features, red: rejected features, yellow: tentative features).

By contrast, using a naive median rank as our consensus importance yields a static pattern of shadow feature importance across permutations (Figure 2).

History of shadow feature importance over Boruta permutations using naive median rank as consensus importance (green: confirmed; red: rejected).

History of shadow feature importance over Boruta permutations using naive median rank as consensus importance (green: confirmed; red: rejected).

The static nature of naive rank is almost certainly due to immediate fixation of feature consensus importance from the first iteration. This is likely because naive rank is not normalized, and for penalized algorithms (XGBoost and lasso), it returns very low rank for most features. These characteristics make this metric less desriable for use in Boruta permutations, as importance estimation does not benefit from shadow feature importance and background estimation.

Using the steps described above, we calculated a normalized median rank for the consensus importance we ultimately used to identify consensus important features. A single Boruta iteration using this metric shows progressive retention of “confirmed” and “tentative” features, and loss of “rejected” features over permutations, indicating this metric does benefit from shadow feature iterations (Figure 3).

History of shadow feature importance with normalized median rank used to calculate consensus importance (green: confirmed; red: rejected; yellow: tentative)

History of shadow feature importance with normalized median rank used to calculate consensus importance (green: confirmed; red: rejected; yellow: tentative)

Comparing consensus importance derived from naive median rank and normalized median rank directly, there is greater variation in importance measured using the latter (Figure 4).

Comparison of median rank measures (naive vs. normalized) across 4 algorithms (lasso: green, XGBoost: blue, Random Forest: orange, and SVM: red).

Comparison of median rank measures (naive vs. normalized) across 4 algorithms (lasso: green, XGBoost: blue, Random Forest: orange, and SVM: red).

Bootstrapping Boruta Permutations

We performed 1000 bootstraps of Boruta permutations for each of five respective importance metrics. Each bootstrap redrew two thirds of the dataset, with preservation of sample group frequency to overall frequency. This was to simulate redrawing training data subsets. The importance metrics applied included:

  1. Consensus importance (normalized median absolute rank, see above).
  2. Lasso importance (Beta-value coefficient).
  3. XGBoost importance (feature importance).
  4. Random Forest Importance (feature importance).
  5. SVM Importance (feature weight).

Code for running bootstraps is described below.

Importance metric functions were defined as follows:


# Importance Functions
  impLasso <- function(df, classes, trainindices, seed=2019){
    # df : data frame to parse, rownames = classifier groupings, colnames = feature ids
    require(glmnet)
    require(SummarizedExperiment)
    set.seed(seed) 
    var.classifier <- response <- as.character(classes)
    y <- factor(response); names(y) <- rownames(df) # response var obj
    x = df # genes of interest
    contrast <- contrasts(y)
    grid <- 10^ seq(10,-2, length=100)
    
    # use cross-validation on the training model.CV only for lambda
    message("performing cross-validation...")
    cv.fit <- cv.glmnet(x[trainindices,], y[trainindices], family = "binomial",
                        type.logistic="modified.Newton", standardize = FALSE,
                        lambda = grid, alpha=1, nfolds = length(trainindices), #LOOCV 
                        type.measure = "class", intercept = FALSE)
    #Select lambda min.
    message("selecting lambda min...")
    lambda.min <- cv.fit$lambda.min
    
    #Fit the full dataset.
    message("fitting whole dataset")
    lassofit <- glmnet(x, y, family = "binomial", standardize = FALSE, 
                       lambda = grid, alpha = 1, intercept = FALSE)
    
    #Extract the coefficients
    lassoimp <- predict(lassofit, type="coefficients", s=lambda.min)
    lassoimp <- lassoimp[2:nrow(lassoimp),1]
    return(lassoimp)
  }
  impRF <- function(df, classes, ntrees=100, seed=2019){
    require(randomForest)
    set.seed(seed)
    class <- as.numeric(classes)
    rffit <- randomForest(class ~ ., data = as.matrix(df), ntree = ntrees,proximity = TRUE)
    # rfimp <- as.numeric(getRFIvar(rfmodel=rffit))
    rfimp <- importance(rffit)[,1]
    return(rfimp)
  }
  impXGB <- function(df, classes, seed=2019){
    require(xgboost)
    set.seed(2019)
    message("fitting xgboost model...")
    xgbfit <- xgboost(data = df, label = classes, max_depth = 2,
                      eta = 1, nthread = 2, nrounds = 2, objective = "binary:logistic")
    message("getting xgboost importances...")
    xgbimp <- xgb.importance(feature_names = colnames(df), model = xgbfit)
    message("reformatting xgb importances...")
    
    xgbimp.format <- c(rep(0, ncol(df)))
    names(xgbimp.format) <- colnames(df)
    for(f in 1:nrow(xgbimp)){
      xgbimp.format[which(colnames(df)==as.character(xgbimp[f,1]))] <- as.numeric(xgbimp[f,2])
    }
    xgbimp.format <- as.numeric(xgbimp.format)
    names(xgbimp.format) <- colnames(df)
    
    return(xgbimp.format)
  }
  impSVM <- function(df, classes, seed=2019){
    require(e1071)
    set.seed(2019)
    message("fitting svm model...")
    svmfit <- svm(as.factor(classes)~., 
                  data=df, 
                  method="C-classification", 
                  kernel="linear")
    svmimp <-  t(svmfit$coefs) %*% svmfit$SV
    message("reformatting importances for output...")
    svmimp.format <- svmimp[1,]
    names(svmimp.format) <- colnames(svmimp)
    return(svmimp.format)
  }
  # CML for Boruta Implementation
  impBorutaCML <- function(x=x, y=y, seed, ranksummary="median",
                           algo.opt=c("lasso","rf","svm","xgb")){
    # impCML
    # Get consensus importance ranks from disparate algorithms.
    # Arguments
    # * df (matrix) : Entire dataset matrix (rows = instances, columns = features)
    # * classes (character): categorizations of instances
    # * algo.opt (list): List of valid algorithms to use for consensus
    # * seed (int): Set the seed for reproducibility
    # * ranksummary (string): Either "score", "median", or "mean", the operation used to calculate consensus rank.
    # Returns:
    # * Consensus rank, optionally a standard output table of importances for selected algorithms (if standtable==TRUE) 
    
    # define the test df if provided or if FALSE
    df.test <- as.matrix(x)
    message("proceeding with df of size ",nrow(df.test))
    classes <- y
    print("getting importances...")
    implist <- list()
    implabellist <- c()
    
    if("lasso" %in% algo.opt){
      # define the trainindices if none provided or FALSE
      message("performing lasso...")
      imp.lasso <- impLasso(df=as.matrix(df.test), 
                            trainindices=seq(1,nrow(df.test)), 
                            classes=classes)
      implist[["lasso"]] <- imp.lasso
      implabellist <- c(implabellist, "lasso")
    }
    if("rf" %in% algo.opt){
      imp.rf <- impRF(df=as.matrix(df.test), classes=classes)
      implist[["rf"]] <- imp.rf
      implabellist <- c(implabellist, "rf")
    }
    if("xgb" %in% algo.opt){
      imp.xgb <- impXGB(df=as.matrix(df.test), classes=classes)
      implist[["xgb"]] <- imp.xgb
      implabellist <- c(implabellist, "xgb")
    }
    if("svm" %in% algo.opt){
      imp.svm <- impSVM(df=as.matrix(df.test), classes=classes)
      implist[["svm"]] <- imp.svm
      implabellist <- c(implabellist, "svm")
    }
    # match importance feature label ordering
    if(length(implist)>1){
      for(i in 1:(length(implist)-1)){
        implist[[i]] <- implist[[i]][order(match(names(implist[[i]]),names(implist[[i+1]])))]
      }
    }
    
    # get importance ranks and rankvars
    if(ranksummary %in% c("median","mean")){
      impranklist <- list()
      # for each rank, calculate normalized rank position
      message("computing normalized rank importances...")
      for(i in 1:length(implist)){
        algoname <- names(implist)[i]
        impvals <- implist[[i]]
        # naive rank
        nranki <- rank(abs(impvals))
        # adj1: compress rank lower bounds
        min.ranki <- min(nranki)
        nranki1 <- nranki
        nranki1[nranki1==min.ranki] <- min(nranki1[!nranki1==min.ranki])-1
        # adj2: normalize rank scale (dif.min/range)
        nranki2 <- nranki1
        nranki2 <- (nranki2-min(nranki2))/(max(nranki2)-min(nranki2))
        # always compute absolute ranks
        impranklist[[algoname]] <- nranki2
        # plot(impvals, nranki, main=algoname)
        # plot(impvals, nranki1, main=algoname)
        # plot(impvals, nranki2, main=algoname)
      }
      medrank <- c()
      meanrank <- c()
      # iterate on features
      for(r in 1:ncol(x)){
        rvalr <- c() # get feature-level ranks
        for(i in 1:length(impranklist)){
          rvalr <- c(rvalr, impranklist[[i]][r]) # append ranks
        }
        # append summarized feature-level ranks, to return
        medrank <- c(medrank, median(rvalr))
        meanrank <- c(meanrank, mean(rvalr))
      }
      # final importance value is directly proportional to summarized rank
      if(ranksummary=="median"){
        lr <- medrank
      } else{
        lr <- meanrank
      }
      message("completed all tasks! Returning...")
      lr
      return(lr)
    }
    
    # get score importance metric
    if(ranksummary=="score"){
      # notes: by-algo score criteria
      # lasso, coeff!=0
      # rf, imp>=90th quantile
      # svm, abs-weight >= 90th quantile
      # xgb, coeff != 0
      featnames <- colnames(x)
      impscore <- rep(0,length(featnames))
      names(impscore) <- colnames(x)
      for(i in 1:length(implist)){
        ni <- names(implist)[i]
        if(ni=="lasso"){
          which.features <- names(implist[[i]][implist[[i]]!=0])
          impscore[which.features] <- impscore[which.features]+1
        }
        if(ni=="xgb"){
          which.features <- names(implist[[i]][implist[[i]]!=0])
          impscore[which.features] <- impscore[which.features]+1
        }
        if(ni=="rf"){
          qrf <- as.numeric(quantile(as.numeric(implist[[i]]), seq(0,1,0.1))[10])
          which.features <- names(implist[[i]][implist[[i]]>=qrf])
          impscore[which.features] <- impscore[which.features]+1
        }
        if(ni=="svm"){
          qsvm <- as.numeric(quantile(abs(as.numeric(implist[[i]])), seq(0,1,0.1))[10])
          which.features <- names(implist[[i]][abs(implist[[i]])>=qsvm])
          impscore[which.features] <- impscore[which.features]+1
        }
      }
      rs <- as.numeric(impscore)
      rs
      return(rs)
    }
    
    return()
  }

Results of Boruta Permutations Bootstraps

After performing bootstraps as described, we analyzed and summarized results.

Summaries Across Importance Functions

We observed the following results from each bootstrap iteration employing one of the five described importance measures.

Feature classification summary across Boruta Bootstraps with Consensus importance (“nrank”). Feature classification summary across Boruta Bootstraps with Lasso importance. Feature classification summary across Boruta Bootstraps with Random Forest importance. Feature classification summary across Boruta Bootstraps with SVM importance. Feature classification summary across Boruta Bootstraps with XGBoost importance. ## Feature Importance Histories Across Runs

Across bootstrap runs with varying importance metrics, we observed the following patterns of feature importnace histories from 4 bootstraps selected at random from each run.

Feature histories across Boruta permutations, from 4 bootstraps drawn at random from each of the 5 runs (green = confirmed, red = rejected, yellow = tentative, blue lines = shadow feature max, mean, and min).

Feature histories across Boruta permutations, from 4 bootstraps drawn at random from each of the 5 runs (green = confirmed, red = rejected, yellow = tentative, blue lines = shadow feature max, mean, and min).

Overlap of Confirmed Features

We also summarized the overlap in confirmed and recurrent confirmed features across bootstrap runs. The following upset plots show subset overlap membership for features confirmed at least once across bootstraps, greater that 5% of bootstraps, or greater than 20% of bootstraps.

Feature overlap among features confirmed in at least 1 bootstrap, across bootstrap runs with 5 importance metrics.

Feature overlap among features confirmed in at least 1 bootstrap, across bootstrap runs with 5 importance metrics.

Feature overlap among features confirmed in at least 5% of bootstrap runs, across bootstrap runs with 5 importance metrics

Feature overlap among features confirmed in at least 5% of bootstrap runs, across bootstrap runs with 5 importance metrics

Feature overlap among features confirmed in at least 20% of bootstrap runs, across bootstrap runs with 5 importance metrics

Feature overlap among features confirmed in at least 20% of bootstrap runs, across bootstrap runs with 5 importance metrics

LS0tCnRpdGxlOiAiUiBOb3RlYm9vayIKb3V0cHV0OgogIHBkZl9kb2N1bWVudDogZGVmYXVsdAogIGh0bWxfbm90ZWJvb2s6IGRlZmF1bHQKLS0tCgpUaGlzIG5vdGVib29rIGRlc2NyaWJlcyBpbXBsZW1lbnRhdGlvbiBvZiB0aGUgQm9ydXRhIHBlcm11dGF0aW9ucyBtZXRob2QgdG8gaWRlbnRpZnkgIGNvbnNlbnN1cyBmZWF0dXJlcyBmcm9tIHRoZSBUQVJHRVQgcGVkaWF0cmljIEFNbCBkYXRhc2V0LgoKIyBNZXRob2RzCgpXZSBhcHBsaWVkIEJvcnV0YSBhcyBpbXBsZW1lbnRlZCBpbiB0aGUgW0JvcnV0YV0oaHR0cHM6Ly9jcmFuLnItcHJvamVjdC5vcmcvd2ViL3BhY2thZ2VzL0JvcnV0YS9pbmRleC5odG1sKSBSIHBhY2thZ2UgKHYuNi4wLjApLiBXZSBpbXBsZW1lbnRlZCB0aGUgQm9ydXRhIHBlcm11YXRhaW9ucyBtZXRob2Qgd2l0aCBhIGNvbnNlbnN1cyByYW5rIGltcG9ydGFuY2UgbWV0cmljLCBhbmQgY29uZHVjdGVkIGJvb3RzdHJhcHMgb2YgZGF0YSBzdWJzZXQgc2VsZWN0aW9uICgyLzNyZHMgb2YgZGF0YSwgdG8gc2ltdWxhdGUgaXRlcmF0aXZlbHkgcmVkcmF3IG9mIHRyYWluaW5nIHNhbXBsZSBzdWJzZXQpLiBFYWNoIEJvcnV0YSBpdGVyYXRpb24gd2FzIGFsbG93ZWQgdG8gcnVuIGZvciB1cCB0byAxMDAgc3RlcHMsIG92ZXIgd2hpY2ggdGhlIGFsZ29yaXRobSBkZXNpZ25hdGVkICJjb25maXJtZWQiLCAidGVudGF0aXZlIiwgYW5kICJyZWplY3RlZCIgZmVhdHVyZXMuCgpIeXBlcnBhcmFtZXRlciBzZXRzIHVzZWQgZm9yIGFsZ29yaXRobSB3aXRoIEJvcnV0YSBwZXJtdWF0YXRpb25zIHdlcmUgaW5mb3JtZWQgYnkgcHJlbGltaW5hcnkgaW52ZXN0aWdhdGlvbiBvZiBtb2RlbCBwZXJmb3JtYW5jZXMgYWNyb3NzIGh5cGVycGFyYW1ldGVyIHNldHMgZm9yIGVhY2ggYWxnb3JpdGhtLiBUaGUgaW5pdGlhbCBkZWZpbmVkIHRyYWluaW5nIGFuZCB0ZXN0IGRhdGEgc3Vic2V0cywgYXMgdXNlZCB0byBtZWFzdXJlIGRpZmZlcmVudGlhbCBnZW5lIGV4cHJlc3Npb24sIHdlcmUgdXNlZCBpbiBoeXBlcnBhcmFtZXRlciBvcHRpbWl6YXRpb24gYW5kIHRvIGRlcml2ZSB0aGUgcmFuay1iYXNlZCBjb25zZW5zdXMgaW1wb3J0YW5jZSBtZWFzdXJlIGFzIGRlc2NyaWJlZCBiZWxvdy4gCgojIyBDb25zZW5zdXMgSW1wb3J0YW5jZSAoJ25yYW5rJykKClRvIGNhbGN1bGF0ZSBhIGNvbnNlbnN1cyBpbXBvcnRhbmNlIG1ldHJpYywgd2UgZGVmaW5lIGEgbWV0aG9kIHRvIHRha2UgdGhlIG1lZGlhbiBub3JtYWxpemVkIGFic29sdXRlIHJhbmsgb2YgZmVhdHVyZXMgZnJvbSBhY3Jvc3MgNCBhbGdvcml0aG1zIChsYXNzbywgWEdCb29zdCwgUmFuZG9tIEZvcmVzdCwgYW5kIFNWTSkuCgpTdGVwcyB0byBjYWxjdWxhdGUgdGhpcyBub3JtYWxpemVkIG1lZGlhbiBpbXBvcnRhbmNlIGluY2x1ZGU6CgoxLiBDYWxjdWxhdGUgYWxnb3JpdGhtLXNwZWNpZmljIGltcG9ydGFuY2VzLgoyLiBUYWtlIGFic29sdXRlIGltcG9ydGFuY2VzIGZyb20gKDEpLgozLiBDYWxjdWxhdGUgbmFpdmUgcmFuayAoaW5kZXgtYmFzZWQpIG9mIGltcG9ydGFuY2VzIGZyb20gKDIpLgo0LiBDYWxjdWFsdGUgbm9ybWFsaXplZCByYW5rIGZyb20gKDMpLgo1LiBDYWxjdWxhdGUgbWVkaWFuIG5vcm1hbGl6ZWQgcmFuayBhbmQgcmV0dXJuLgoKV2Ugc2V0dGxlZCBvbiB0aGlzIHN0cmF0ZWd5IGR1ZSB0byBwcm9wZXJ0aWVzIG9mIEJvcnV0YSBhbmQgZmVhdHVyZSBzZWxlY3Rpb24uIEZvciBjb21wYXJpc29uLCBhIHN0YW5kYXJkIG9mIEJvcnV0YSB1c2luZyBSYW5kb20gRm9yZXN0IGltcG9ydGFuY2Ugc2hvd3Mgb3NjaWxsYXRpb24gb2Ygc2hhZG93IGZlYXR1cmUgaW1wb3J0YW5jZXMsIGdyYWR1YWwgZXhjbHVzaW9uIG9mIHJlamVjdGVkIGZlYXR1cmVzLCBhbmQgcmV0ZW50aW9uIG9mIGltcG9ydGFudCBmZWF0dXJlcyAoRmlndXJlIDEpIAoKIVtIaXN0b3J5IG9mIHNoYWRvdyBmZWF0dXJlIGltcG9ydGFuY2VzIG92ZXIgcGVybXVhdGF0aW9ucyBpbiBhIHNpbmdsZSBCb3J1dGEgaXRlcmF0aW9uIHVzaW5nIFJhbmRvbSBGb3Jlc3QgaW1wb3J0YW5jZSAoZ3JlZW46IGNvbmZpcm1lZCBmZWF0dXJlcywgcmVkOiByZWplY3RlZCBmZWF0dXJlcywgeWVsbG93OiB0ZW50YXRpdmUgZmVhdHVyZXMpLl0oYnJmX2ltcGhpc3RfbGluZXBsb3QuanBlZykKCkJ5IGNvbnRyYXN0LCB1c2luZyBhIG5haXZlIG1lZGlhbiByYW5rIGFzIG91ciBjb25zZW5zdXMgaW1wb3J0YW5jZSB5aWVsZHMgYSBzdGF0aWMgcGF0dGVybiBvZiBzaGFkb3cgZmVhdHVyZSBpbXBvcnRhbmNlIGFjcm9zcyBwZXJtdXRhdGlvbnMgKEZpZ3VyZSAyKS4KCiFbSGlzdG9yeSBvZiBzaGFkb3cgZmVhdHVyZSBpbXBvcnRhbmNlIG92ZXIgQm9ydXRhIHBlcm11dGF0aW9ucyB1c2luZyBuYWl2ZSBtZWRpYW4gcmFuayBhcyBjb25zZW5zdXMgaW1wb3J0YW5jZSAoZ3JlZW46IGNvbmZpcm1lZDsgcmVkOiByZWplY3RlZCkuXShib3J1dGFoaXN0X25haXZlbWVkaWFucmFuay5wbmcpCgpUaGUgc3RhdGljIG5hdHVyZSBvZiBuYWl2ZSByYW5rIGlzIGFsbW9zdCBjZXJ0YWlubHkgZHVlIHRvIGltbWVkaWF0ZSBmaXhhdGlvbiBvZiBmZWF0dXJlIGNvbnNlbnN1cyBpbXBvcnRhbmNlIGZyb20gdGhlIGZpcnN0IGl0ZXJhdGlvbi4gVGhpcyBpcyBsaWtlbHkgYmVjYXVzZSBuYWl2ZSByYW5rIGlzIG5vdCBub3JtYWxpemVkLCBhbmQgZm9yIHBlbmFsaXplZCBhbGdvcml0aG1zIChYR0Jvb3N0IGFuZCBsYXNzbyksIGl0IHJldHVybnMgdmVyeSBsb3cgcmFuayBmb3IgbW9zdCBmZWF0dXJlcy4gVGhlc2UgY2hhcmFjdGVyaXN0aWNzIG1ha2UgdGhpcyBtZXRyaWMgbGVzcyBkZXNyaWFibGUgZm9yIHVzZSBpbiBCb3J1dGEgcGVybXV0YXRpb25zLCBhcyBpbXBvcnRhbmNlIGVzdGltYXRpb24gZG9lcyBub3QgYmVuZWZpdCBmcm9tIHNoYWRvdyBmZWF0dXJlIGltcG9ydGFuY2UgYW5kIGJhY2tncm91bmQgZXN0aW1hdGlvbi4KClVzaW5nIHRoZSBzdGVwcyBkZXNjcmliZWQgYWJvdmUsIHdlIGNhbGN1bGF0ZWQgYSBub3JtYWxpemVkIG1lZGlhbiByYW5rIGZvciB0aGUgY29uc2Vuc3VzIGltcG9ydGFuY2Ugd2UgdWx0aW1hdGVseSB1c2VkIHRvIGlkZW50aWZ5IGNvbnNlbnN1cyBpbXBvcnRhbnQgZmVhdHVyZXMuIEEgc2luZ2xlIEJvcnV0YSBpdGVyYXRpb24gdXNpbmcgdGhpcyBtZXRyaWMgc2hvd3MgcHJvZ3Jlc3NpdmUgcmV0ZW50aW9uIG9mICJjb25maXJtZWQiIGFuZCAidGVudGF0aXZlIiBmZWF0dXJlcywgYW5kIGxvc3Mgb2YgInJlamVjdGVkIiBmZWF0dXJlcyBvdmVyIHBlcm11dGF0aW9ucywgaW5kaWNhdGluZyB0aGlzIG1ldHJpYyBkb2VzIGJlbmVmaXQgZnJvbSBzaGFkb3cgZmVhdHVyZSBpdGVyYXRpb25zIChGaWd1cmUgMykuCgohW0hpc3Rvcnkgb2Ygc2hhZG93IGZlYXR1cmUgaW1wb3J0YW5jZSB3aXRoIG5vcm1hbGl6ZWQgbWVkaWFuIHJhbmsgdXNlZCB0byBjYWxjdWxhdGUgY29uc2Vuc3VzIGltcG9ydGFuY2UgKGdyZWVuOiBjb25maXJtZWQ7IHJlZDogcmVqZWN0ZWQ7IHllbGxvdzogdGVudGF0aXZlKV0oYm9ydXRhaXRlci1pbXBoaXN0X25yYW5rLmpwZWcpCgpDb21wYXJpbmcgY29uc2Vuc3VzIGltcG9ydGFuY2UgZGVyaXZlZCBmcm9tIG5haXZlIG1lZGlhbiByYW5rIGFuZCBub3JtYWxpemVkIG1lZGlhbiByYW5rIGRpcmVjdGx5LCB0aGVyZSBpcyBncmVhdGVyIHZhcmlhdGlvbiBpbiBpbXBvcnRhbmNlIG1lYXN1cmVkIHVzaW5nIHRoZSBsYXR0ZXIgKEZpZ3VyZSA0KS4KCiFbQ29tcGFyaXNvbiBvZiBtZWRpYW4gcmFuayBtZWFzdXJlcyAobmFpdmUgdnMuIG5vcm1hbGl6ZWQpIGFjcm9zcyA0IGFsZ29yaXRobXMgKGxhc3NvOiBncmVlbiwgWEdCb29zdDogYmx1ZSwgUmFuZG9tIEZvcmVzdDogb3JhbmdlLCBhbmQgU1ZNOiByZWQpLiBdKHJhbmtjb21wYXJlXzRhbGdvLmpwZykKCiMjIEJvb3RzdHJhcHBpbmcgQm9ydXRhIFBlcm11dGF0aW9ucwoKV2UgcGVyZm9ybWVkIDEwMDAgYm9vdHN0cmFwcyBvZiBCb3J1dGEgcGVybXV0YXRpb25zIGZvciBlYWNoIG9mIGZpdmUgcmVzcGVjdGl2ZSBpbXBvcnRhbmNlIG1ldHJpY3MuIEVhY2ggYm9vdHN0cmFwIHJlZHJldyB0d28gdGhpcmRzIG9mIHRoZSBkYXRhc2V0LCB3aXRoIHByZXNlcnZhdGlvbiBvZiBzYW1wbGUgZ3JvdXAgZnJlcXVlbmN5IHRvIG92ZXJhbGwgZnJlcXVlbmN5LiBUaGlzIHdhcyB0byBzaW11bGF0ZSByZWRyYXdpbmcgdHJhaW5pbmcgZGF0YSBzdWJzZXRzLiBUaGUgaW1wb3J0YW5jZSBtZXRyaWNzIGFwcGxpZWQgaW5jbHVkZWQ6CgoxLiBDb25zZW5zdXMgaW1wb3J0YW5jZSAobm9ybWFsaXplZCBtZWRpYW4gYWJzb2x1dGUgcmFuaywgc2VlIGFib3ZlKS4KMi4gTGFzc28gaW1wb3J0YW5jZSAoQmV0YS12YWx1ZSBjb2VmZmljaWVudCkuCjMuIFhHQm9vc3QgaW1wb3J0YW5jZSAoZmVhdHVyZSBpbXBvcnRhbmNlKS4KNC4gUmFuZG9tIEZvcmVzdCBJbXBvcnRhbmNlIChmZWF0dXJlIGltcG9ydGFuY2UpLgo1LiBTVk0gSW1wb3J0YW5jZSAoZmVhdHVyZSB3ZWlnaHQpLgoKQ29kZSBmb3IgcnVubmluZyBib290c3RyYXBzIGlzIGRlc2NyaWJlZCBiZWxvdy4KCkltcG9ydGFuY2UgbWV0cmljIGZ1bmN0aW9ucyB3ZXJlIGRlZmluZWQgYXMgZm9sbG93czoKYGBge3IsIGltcE1ldHJpY3N9CgojIEltcG9ydGFuY2UgRnVuY3Rpb25zCiAgaW1wTGFzc28gPC0gZnVuY3Rpb24oZGYsIGNsYXNzZXMsIHRyYWluaW5kaWNlcywgc2VlZD0yMDE5KXsKICAgICMgZGYgOiBkYXRhIGZyYW1lIHRvIHBhcnNlLCByb3duYW1lcyA9IGNsYXNzaWZpZXIgZ3JvdXBpbmdzLCBjb2xuYW1lcyA9IGZlYXR1cmUgaWRzCiAgICByZXF1aXJlKGdsbW5ldCkKICAgIHJlcXVpcmUoU3VtbWFyaXplZEV4cGVyaW1lbnQpCiAgICBzZXQuc2VlZChzZWVkKSAKICAgIHZhci5jbGFzc2lmaWVyIDwtIHJlc3BvbnNlIDwtIGFzLmNoYXJhY3RlcihjbGFzc2VzKQogICAgeSA8LSBmYWN0b3IocmVzcG9uc2UpOyBuYW1lcyh5KSA8LSByb3duYW1lcyhkZikgIyByZXNwb25zZSB2YXIgb2JqCiAgICB4ID0gZGYgIyBnZW5lcyBvZiBpbnRlcmVzdAogICAgY29udHJhc3QgPC0gY29udHJhc3RzKHkpCiAgICBncmlkIDwtIDEwXiBzZXEoMTAsLTIsIGxlbmd0aD0xMDApCiAgICAKICAgICMgdXNlIGNyb3NzLXZhbGlkYXRpb24gb24gdGhlIHRyYWluaW5nIG1vZGVsLkNWIG9ubHkgZm9yIGxhbWJkYQogICAgbWVzc2FnZSgicGVyZm9ybWluZyBjcm9zcy12YWxpZGF0aW9uLi4uIikKICAgIGN2LmZpdCA8LSBjdi5nbG1uZXQoeFt0cmFpbmluZGljZXMsXSwgeVt0cmFpbmluZGljZXNdLCBmYW1pbHkgPSAiYmlub21pYWwiLAogICAgICAgICAgICAgICAgICAgICAgICB0eXBlLmxvZ2lzdGljPSJtb2RpZmllZC5OZXd0b24iLCBzdGFuZGFyZGl6ZSA9IEZBTFNFLAogICAgICAgICAgICAgICAgICAgICAgICBsYW1iZGEgPSBncmlkLCBhbHBoYT0xLCBuZm9sZHMgPSBsZW5ndGgodHJhaW5pbmRpY2VzKSwgI0xPT0NWIAogICAgICAgICAgICAgICAgICAgICAgICB0eXBlLm1lYXN1cmUgPSAiY2xhc3MiLCBpbnRlcmNlcHQgPSBGQUxTRSkKICAgICNTZWxlY3QgbGFtYmRhIG1pbi4KICAgIG1lc3NhZ2UoInNlbGVjdGluZyBsYW1iZGEgbWluLi4uIikKICAgIGxhbWJkYS5taW4gPC0gY3YuZml0JGxhbWJkYS5taW4KICAgIAogICAgI0ZpdCB0aGUgZnVsbCBkYXRhc2V0LgogICAgbWVzc2FnZSgiZml0dGluZyB3aG9sZSBkYXRhc2V0IikKICAgIGxhc3NvZml0IDwtIGdsbW5ldCh4LCB5LCBmYW1pbHkgPSAiYmlub21pYWwiLCBzdGFuZGFyZGl6ZSA9IEZBTFNFLCAKICAgICAgICAgICAgICAgICAgICAgICBsYW1iZGEgPSBncmlkLCBhbHBoYSA9IDEsIGludGVyY2VwdCA9IEZBTFNFKQogICAgCiAgICAjRXh0cmFjdCB0aGUgY29lZmZpY2llbnRzCiAgICBsYXNzb2ltcCA8LSBwcmVkaWN0KGxhc3NvZml0LCB0eXBlPSJjb2VmZmljaWVudHMiLCBzPWxhbWJkYS5taW4pCiAgICBsYXNzb2ltcCA8LSBsYXNzb2ltcFsyOm5yb3cobGFzc29pbXApLDFdCiAgICByZXR1cm4obGFzc29pbXApCiAgfQogIGltcFJGIDwtIGZ1bmN0aW9uKGRmLCBjbGFzc2VzLCBudHJlZXM9MTAwLCBzZWVkPTIwMTkpewogICAgcmVxdWlyZShyYW5kb21Gb3Jlc3QpCiAgICBzZXQuc2VlZChzZWVkKQogICAgY2xhc3MgPC0gYXMubnVtZXJpYyhjbGFzc2VzKQogICAgcmZmaXQgPC0gcmFuZG9tRm9yZXN0KGNsYXNzIH4gLiwgZGF0YSA9IGFzLm1hdHJpeChkZiksIG50cmVlID0gbnRyZWVzLHByb3hpbWl0eSA9IFRSVUUpCiAgICAjIHJmaW1wIDwtIGFzLm51bWVyaWMoZ2V0UkZJdmFyKHJmbW9kZWw9cmZmaXQpKQogICAgcmZpbXAgPC0gaW1wb3J0YW5jZShyZmZpdClbLDFdCiAgICByZXR1cm4ocmZpbXApCiAgfQogIGltcFhHQiA8LSBmdW5jdGlvbihkZiwgY2xhc3Nlcywgc2VlZD0yMDE5KXsKICAgIHJlcXVpcmUoeGdib29zdCkKICAgIHNldC5zZWVkKDIwMTkpCiAgICBtZXNzYWdlKCJmaXR0aW5nIHhnYm9vc3QgbW9kZWwuLi4iKQogICAgeGdiZml0IDwtIHhnYm9vc3QoZGF0YSA9IGRmLCBsYWJlbCA9IGNsYXNzZXMsIG1heF9kZXB0aCA9IDIsCiAgICAgICAgICAgICAgICAgICAgICBldGEgPSAxLCBudGhyZWFkID0gMiwgbnJvdW5kcyA9IDIsIG9iamVjdGl2ZSA9ICJiaW5hcnk6bG9naXN0aWMiKQogICAgbWVzc2FnZSgiZ2V0dGluZyB4Z2Jvb3N0IGltcG9ydGFuY2VzLi4uIikKICAgIHhnYmltcCA8LSB4Z2IuaW1wb3J0YW5jZShmZWF0dXJlX25hbWVzID0gY29sbmFtZXMoZGYpLCBtb2RlbCA9IHhnYmZpdCkKICAgIG1lc3NhZ2UoInJlZm9ybWF0dGluZyB4Z2IgaW1wb3J0YW5jZXMuLi4iKQogICAgCiAgICB4Z2JpbXAuZm9ybWF0IDwtIGMocmVwKDAsIG5jb2woZGYpKSkKICAgIG5hbWVzKHhnYmltcC5mb3JtYXQpIDwtIGNvbG5hbWVzKGRmKQogICAgZm9yKGYgaW4gMTpucm93KHhnYmltcCkpewogICAgICB4Z2JpbXAuZm9ybWF0W3doaWNoKGNvbG5hbWVzKGRmKT09YXMuY2hhcmFjdGVyKHhnYmltcFtmLDFdKSldIDwtIGFzLm51bWVyaWMoeGdiaW1wW2YsMl0pCiAgICB9CiAgICB4Z2JpbXAuZm9ybWF0IDwtIGFzLm51bWVyaWMoeGdiaW1wLmZvcm1hdCkKICAgIG5hbWVzKHhnYmltcC5mb3JtYXQpIDwtIGNvbG5hbWVzKGRmKQogICAgCiAgICByZXR1cm4oeGdiaW1wLmZvcm1hdCkKICB9CiAgaW1wU1ZNIDwtIGZ1bmN0aW9uKGRmLCBjbGFzc2VzLCBzZWVkPTIwMTkpewogICAgcmVxdWlyZShlMTA3MSkKICAgIHNldC5zZWVkKDIwMTkpCiAgICBtZXNzYWdlKCJmaXR0aW5nIHN2bSBtb2RlbC4uLiIpCiAgICBzdm1maXQgPC0gc3ZtKGFzLmZhY3RvcihjbGFzc2VzKX4uLCAKICAgICAgICAgICAgICAgICAgZGF0YT1kZiwgCiAgICAgICAgICAgICAgICAgIG1ldGhvZD0iQy1jbGFzc2lmaWNhdGlvbiIsIAogICAgICAgICAgICAgICAgICBrZXJuZWw9ImxpbmVhciIpCiAgICBzdm1pbXAgPC0gIHQoc3ZtZml0JGNvZWZzKSAlKiUgc3ZtZml0JFNWCiAgICBtZXNzYWdlKCJyZWZvcm1hdHRpbmcgaW1wb3J0YW5jZXMgZm9yIG91dHB1dC4uLiIpCiAgICBzdm1pbXAuZm9ybWF0IDwtIHN2bWltcFsxLF0KICAgIG5hbWVzKHN2bWltcC5mb3JtYXQpIDwtIGNvbG5hbWVzKHN2bWltcCkKICAgIHJldHVybihzdm1pbXAuZm9ybWF0KQogIH0KICAjIENNTCBmb3IgQm9ydXRhIEltcGxlbWVudGF0aW9uCiAgaW1wQm9ydXRhQ01MIDwtIGZ1bmN0aW9uKHg9eCwgeT15LCBzZWVkLCByYW5rc3VtbWFyeT0ibWVkaWFuIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgYWxnby5vcHQ9YygibGFzc28iLCJyZiIsInN2bSIsInhnYiIpKXsKICAgICMgaW1wQ01MCiAgICAjIEdldCBjb25zZW5zdXMgaW1wb3J0YW5jZSByYW5rcyBmcm9tIGRpc3BhcmF0ZSBhbGdvcml0aG1zLgogICAgIyBBcmd1bWVudHMKICAgICMgKiBkZiAobWF0cml4KSA6IEVudGlyZSBkYXRhc2V0IG1hdHJpeCAocm93cyA9IGluc3RhbmNlcywgY29sdW1ucyA9IGZlYXR1cmVzKQogICAgIyAqIGNsYXNzZXMgKGNoYXJhY3Rlcik6IGNhdGVnb3JpemF0aW9ucyBvZiBpbnN0YW5jZXMKICAgICMgKiBhbGdvLm9wdCAobGlzdCk6IExpc3Qgb2YgdmFsaWQgYWxnb3JpdGhtcyB0byB1c2UgZm9yIGNvbnNlbnN1cwogICAgIyAqIHNlZWQgKGludCk6IFNldCB0aGUgc2VlZCBmb3IgcmVwcm9kdWNpYmlsaXR5CiAgICAjICogcmFua3N1bW1hcnkgKHN0cmluZyk6IEVpdGhlciAic2NvcmUiLCAibWVkaWFuIiwgb3IgIm1lYW4iLCB0aGUgb3BlcmF0aW9uIHVzZWQgdG8gY2FsY3VsYXRlIGNvbnNlbnN1cyByYW5rLgogICAgIyBSZXR1cm5zOgogICAgIyAqIENvbnNlbnN1cyByYW5rLCBvcHRpb25hbGx5IGEgc3RhbmRhcmQgb3V0cHV0IHRhYmxlIG9mIGltcG9ydGFuY2VzIGZvciBzZWxlY3RlZCBhbGdvcml0aG1zIChpZiBzdGFuZHRhYmxlPT1UUlVFKSAKICAgIAogICAgIyBkZWZpbmUgdGhlIHRlc3QgZGYgaWYgcHJvdmlkZWQgb3IgaWYgRkFMU0UKICAgIGRmLnRlc3QgPC0gYXMubWF0cml4KHgpCiAgICBtZXNzYWdlKCJwcm9jZWVkaW5nIHdpdGggZGYgb2Ygc2l6ZSAiLG5yb3coZGYudGVzdCkpCiAgICBjbGFzc2VzIDwtIHkKICAgIHByaW50KCJnZXR0aW5nIGltcG9ydGFuY2VzLi4uIikKICAgIGltcGxpc3QgPC0gbGlzdCgpCiAgICBpbXBsYWJlbGxpc3QgPC0gYygpCiAgICAKICAgIGlmKCJsYXNzbyIgJWluJSBhbGdvLm9wdCl7CiAgICAgICMgZGVmaW5lIHRoZSB0cmFpbmluZGljZXMgaWYgbm9uZSBwcm92aWRlZCBvciBGQUxTRQogICAgICBtZXNzYWdlKCJwZXJmb3JtaW5nIGxhc3NvLi4uIikKICAgICAgaW1wLmxhc3NvIDwtIGltcExhc3NvKGRmPWFzLm1hdHJpeChkZi50ZXN0KSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB0cmFpbmluZGljZXM9c2VxKDEsbnJvdyhkZi50ZXN0KSksIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgY2xhc3Nlcz1jbGFzc2VzKQogICAgICBpbXBsaXN0W1sibGFzc28iXV0gPC0gaW1wLmxhc3NvCiAgICAgIGltcGxhYmVsbGlzdCA8LSBjKGltcGxhYmVsbGlzdCwgImxhc3NvIikKICAgIH0KICAgIGlmKCJyZiIgJWluJSBhbGdvLm9wdCl7CiAgICAgIGltcC5yZiA8LSBpbXBSRihkZj1hcy5tYXRyaXgoZGYudGVzdCksIGNsYXNzZXM9Y2xhc3NlcykKICAgICAgaW1wbGlzdFtbInJmIl1dIDwtIGltcC5yZgogICAgICBpbXBsYWJlbGxpc3QgPC0gYyhpbXBsYWJlbGxpc3QsICJyZiIpCiAgICB9CiAgICBpZigieGdiIiAlaW4lIGFsZ28ub3B0KXsKICAgICAgaW1wLnhnYiA8LSBpbXBYR0IoZGY9YXMubWF0cml4KGRmLnRlc3QpLCBjbGFzc2VzPWNsYXNzZXMpCiAgICAgIGltcGxpc3RbWyJ4Z2IiXV0gPC0gaW1wLnhnYgogICAgICBpbXBsYWJlbGxpc3QgPC0gYyhpbXBsYWJlbGxpc3QsICJ4Z2IiKQogICAgfQogICAgaWYoInN2bSIgJWluJSBhbGdvLm9wdCl7CiAgICAgIGltcC5zdm0gPC0gaW1wU1ZNKGRmPWFzLm1hdHJpeChkZi50ZXN0KSwgY2xhc3Nlcz1jbGFzc2VzKQogICAgICBpbXBsaXN0W1sic3ZtIl1dIDwtIGltcC5zdm0KICAgICAgaW1wbGFiZWxsaXN0IDwtIGMoaW1wbGFiZWxsaXN0LCAic3ZtIikKICAgIH0KICAgICMgbWF0Y2ggaW1wb3J0YW5jZSBmZWF0dXJlIGxhYmVsIG9yZGVyaW5nCiAgICBpZihsZW5ndGgoaW1wbGlzdCk+MSl7CiAgICAgIGZvcihpIGluIDE6KGxlbmd0aChpbXBsaXN0KS0xKSl7CiAgICAgICAgaW1wbGlzdFtbaV1dIDwtIGltcGxpc3RbW2ldXVtvcmRlcihtYXRjaChuYW1lcyhpbXBsaXN0W1tpXV0pLG5hbWVzKGltcGxpc3RbW2krMV1dKSkpXQogICAgICB9CiAgICB9CiAgICAKICAgICMgZ2V0IGltcG9ydGFuY2UgcmFua3MgYW5kIHJhbmt2YXJzCiAgICBpZihyYW5rc3VtbWFyeSAlaW4lIGMoIm1lZGlhbiIsIm1lYW4iKSl7CiAgICAgIGltcHJhbmtsaXN0IDwtIGxpc3QoKQogICAgICAjIGZvciBlYWNoIHJhbmssIGNhbGN1bGF0ZSBub3JtYWxpemVkIHJhbmsgcG9zaXRpb24KICAgICAgbWVzc2FnZSgiY29tcHV0aW5nIG5vcm1hbGl6ZWQgcmFuayBpbXBvcnRhbmNlcy4uLiIpCiAgICAgIGZvcihpIGluIDE6bGVuZ3RoKGltcGxpc3QpKXsKICAgICAgICBhbGdvbmFtZSA8LSBuYW1lcyhpbXBsaXN0KVtpXQogICAgICAgIGltcHZhbHMgPC0gaW1wbGlzdFtbaV1dCiAgICAgICAgIyBuYWl2ZSByYW5rCiAgICAgICAgbnJhbmtpIDwtIHJhbmsoYWJzKGltcHZhbHMpKQogICAgICAgICMgYWRqMTogY29tcHJlc3MgcmFuayBsb3dlciBib3VuZHMKICAgICAgICBtaW4ucmFua2kgPC0gbWluKG5yYW5raSkKICAgICAgICBucmFua2kxIDwtIG5yYW5raQogICAgICAgIG5yYW5raTFbbnJhbmtpMT09bWluLnJhbmtpXSA8LSBtaW4obnJhbmtpMVshbnJhbmtpMT09bWluLnJhbmtpXSktMQogICAgICAgICMgYWRqMjogbm9ybWFsaXplIHJhbmsgc2NhbGUgKGRpZi5taW4vcmFuZ2UpCiAgICAgICAgbnJhbmtpMiA8LSBucmFua2kxCiAgICAgICAgbnJhbmtpMiA8LSAobnJhbmtpMi1taW4obnJhbmtpMikpLyhtYXgobnJhbmtpMiktbWluKG5yYW5raTIpKQogICAgICAgICMgYWx3YXlzIGNvbXB1dGUgYWJzb2x1dGUgcmFua3MKICAgICAgICBpbXByYW5rbGlzdFtbYWxnb25hbWVdXSA8LSBucmFua2kyCiAgICAgICAgIyBwbG90KGltcHZhbHMsIG5yYW5raSwgbWFpbj1hbGdvbmFtZSkKICAgICAgICAjIHBsb3QoaW1wdmFscywgbnJhbmtpMSwgbWFpbj1hbGdvbmFtZSkKICAgICAgICAjIHBsb3QoaW1wdmFscywgbnJhbmtpMiwgbWFpbj1hbGdvbmFtZSkKICAgICAgfQogICAgICBtZWRyYW5rIDwtIGMoKQogICAgICBtZWFucmFuayA8LSBjKCkKICAgICAgIyBpdGVyYXRlIG9uIGZlYXR1cmVzCiAgICAgIGZvcihyIGluIDE6bmNvbCh4KSl7CiAgICAgICAgcnZhbHIgPC0gYygpICMgZ2V0IGZlYXR1cmUtbGV2ZWwgcmFua3MKICAgICAgICBmb3IoaSBpbiAxOmxlbmd0aChpbXByYW5rbGlzdCkpewogICAgICAgICAgcnZhbHIgPC0gYyhydmFsciwgaW1wcmFua2xpc3RbW2ldXVtyXSkgIyBhcHBlbmQgcmFua3MKICAgICAgICB9CiAgICAgICAgIyBhcHBlbmQgc3VtbWFyaXplZCBmZWF0dXJlLWxldmVsIHJhbmtzLCB0byByZXR1cm4KICAgICAgICBtZWRyYW5rIDwtIGMobWVkcmFuaywgbWVkaWFuKHJ2YWxyKSkKICAgICAgICBtZWFucmFuayA8LSBjKG1lYW5yYW5rLCBtZWFuKHJ2YWxyKSkKICAgICAgfQogICAgICAjIGZpbmFsIGltcG9ydGFuY2UgdmFsdWUgaXMgZGlyZWN0bHkgcHJvcG9ydGlvbmFsIHRvIHN1bW1hcml6ZWQgcmFuawogICAgICBpZihyYW5rc3VtbWFyeT09Im1lZGlhbiIpewogICAgICAgIGxyIDwtIG1lZHJhbmsKICAgICAgfSBlbHNlewogICAgICAgIGxyIDwtIG1lYW5yYW5rCiAgICAgIH0KICAgICAgbWVzc2FnZSgiY29tcGxldGVkIGFsbCB0YXNrcyEgUmV0dXJuaW5nLi4uIikKICAgICAgbHIKICAgICAgcmV0dXJuKGxyKQogICAgfQogICAgCiAgICAjIGdldCBzY29yZSBpbXBvcnRhbmNlIG1ldHJpYwogICAgaWYocmFua3N1bW1hcnk9PSJzY29yZSIpewogICAgICAjIG5vdGVzOiBieS1hbGdvIHNjb3JlIGNyaXRlcmlhCiAgICAgICMgbGFzc28sIGNvZWZmIT0wCiAgICAgICMgcmYsIGltcD49OTB0aCBxdWFudGlsZQogICAgICAjIHN2bSwgYWJzLXdlaWdodCA+PSA5MHRoIHF1YW50aWxlCiAgICAgICMgeGdiLCBjb2VmZiAhPSAwCiAgICAgIGZlYXRuYW1lcyA8LSBjb2xuYW1lcyh4KQogICAgICBpbXBzY29yZSA8LSByZXAoMCxsZW5ndGgoZmVhdG5hbWVzKSkKICAgICAgbmFtZXMoaW1wc2NvcmUpIDwtIGNvbG5hbWVzKHgpCiAgICAgIGZvcihpIGluIDE6bGVuZ3RoKGltcGxpc3QpKXsKICAgICAgICBuaSA8LSBuYW1lcyhpbXBsaXN0KVtpXQogICAgICAgIGlmKG5pPT0ibGFzc28iKXsKICAgICAgICAgIHdoaWNoLmZlYXR1cmVzIDwtIG5hbWVzKGltcGxpc3RbW2ldXVtpbXBsaXN0W1tpXV0hPTBdKQogICAgICAgICAgaW1wc2NvcmVbd2hpY2guZmVhdHVyZXNdIDwtIGltcHNjb3JlW3doaWNoLmZlYXR1cmVzXSsxCiAgICAgICAgfQogICAgICAgIGlmKG5pPT0ieGdiIil7CiAgICAgICAgICB3aGljaC5mZWF0dXJlcyA8LSBuYW1lcyhpbXBsaXN0W1tpXV1baW1wbGlzdFtbaV1dIT0wXSkKICAgICAgICAgIGltcHNjb3JlW3doaWNoLmZlYXR1cmVzXSA8LSBpbXBzY29yZVt3aGljaC5mZWF0dXJlc10rMQogICAgICAgIH0KICAgICAgICBpZihuaT09InJmIil7CiAgICAgICAgICBxcmYgPC0gYXMubnVtZXJpYyhxdWFudGlsZShhcy5udW1lcmljKGltcGxpc3RbW2ldXSksIHNlcSgwLDEsMC4xKSlbMTBdKQogICAgICAgICAgd2hpY2guZmVhdHVyZXMgPC0gbmFtZXMoaW1wbGlzdFtbaV1dW2ltcGxpc3RbW2ldXT49cXJmXSkKICAgICAgICAgIGltcHNjb3JlW3doaWNoLmZlYXR1cmVzXSA8LSBpbXBzY29yZVt3aGljaC5mZWF0dXJlc10rMQogICAgICAgIH0KICAgICAgICBpZihuaT09InN2bSIpewogICAgICAgICAgcXN2bSA8LSBhcy5udW1lcmljKHF1YW50aWxlKGFicyhhcy5udW1lcmljKGltcGxpc3RbW2ldXSkpLCBzZXEoMCwxLDAuMSkpWzEwXSkKICAgICAgICAgIHdoaWNoLmZlYXR1cmVzIDwtIG5hbWVzKGltcGxpc3RbW2ldXVthYnMoaW1wbGlzdFtbaV1dKT49cXN2bV0pCiAgICAgICAgICBpbXBzY29yZVt3aGljaC5mZWF0dXJlc10gPC0gaW1wc2NvcmVbd2hpY2guZmVhdHVyZXNdKzEKICAgICAgICB9CiAgICAgIH0KICAgICAgcnMgPC0gYXMubnVtZXJpYyhpbXBzY29yZSkKICAgICAgcnMKICAgICAgcmV0dXJuKHJzKQogICAgfQogICAgCiAgICByZXR1cm4oKQogIH0KCmBgYAoKIyBSZXN1bHRzIG9mIEJvcnV0YSBQZXJtdXRhdGlvbnMgQm9vdHN0cmFwcwoKQWZ0ZXIgcGVyZm9ybWluZyBib290c3RyYXBzIGFzIGRlc2NyaWJlZCwgd2UgYW5hbHl6ZWQgYW5kIHN1bW1hcml6ZWQgcmVzdWx0cy4gCgojIyBTdW1tYXJpZXMgQWNyb3NzIEltcG9ydGFuY2UgRnVuY3Rpb25zCgpXZSBvYnNlcnZlZCB0aGUgZm9sbG93aW5nIHJlc3VsdHMgZnJvbSBlYWNoIGJvb3RzdHJhcCBpdGVyYXRpb24gZW1wbG95aW5nIG9uZSBvZiB0aGUgZml2ZSBkZXNjcmliZWQgaW1wb3J0YW5jZSBtZWFzdXJlcy4KCiFbRmVhdHVyZSBjbGFzc2lmaWNhdGlvbiBzdW1tYXJ5IGFjcm9zcyBCb3J1dGEgQm9vdHN0cmFwcyB3aXRoIENvbnNlbnN1cyBpbXBvcnRhbmNlICgibnJhbmsiKS5dKGJicy1ucmFua19jb21wcGxvdC5qcGcpCiFbRmVhdHVyZSBjbGFzc2lmaWNhdGlvbiBzdW1tYXJ5IGFjcm9zcyBCb3J1dGEgQm9vdHN0cmFwcyB3aXRoIExhc3NvIGltcG9ydGFuY2UuXShiYnMtbGFzc29fY29tcHBsb3QuanBnKQohW0ZlYXR1cmUgY2xhc3NpZmljYXRpb24gc3VtbWFyeSBhY3Jvc3MgQm9ydXRhIEJvb3RzdHJhcHMgd2l0aCBSYW5kb20gRm9yZXN0IGltcG9ydGFuY2UuXShiYnMtcmZfY29tcHBsb3QuanBnKQohW0ZlYXR1cmUgY2xhc3NpZmljYXRpb24gc3VtbWFyeSBhY3Jvc3MgQm9ydXRhIEJvb3RzdHJhcHMgd2l0aCBTVk0gaW1wb3J0YW5jZS5dKGJicy1zdm1fY29tcHBsb3QuanBnKQohW0ZlYXR1cmUgY2xhc3NpZmljYXRpb24gc3VtbWFyeSBhY3Jvc3MgQm9ydXRhIEJvb3RzdHJhcHMgd2l0aCBYR0Jvb3N0IGltcG9ydGFuY2UuXShiYnMteGdiX2NvbXBwbG90LmpwZykKIyMgRmVhdHVyZSBJbXBvcnRhbmNlIEhpc3RvcmllcyBBY3Jvc3MgUnVucwoKQWNyb3NzIGJvb3RzdHJhcCBydW5zIHdpdGggdmFyeWluZyBpbXBvcnRhbmNlIG1ldHJpY3MsIHdlIG9ic2VydmVkIHRoZSBmb2xsb3dpbmcgcGF0dGVybnMgb2YgZmVhdHVyZSBpbXBvcnRuYWNlIGhpc3RvcmllcyBmcm9tIDQgYm9vdHN0cmFwcyBzZWxlY3RlZCBhdCByYW5kb20gZnJvbSBlYWNoIHJ1bi4KCiFbRmVhdHVyZSBoaXN0b3JpZXMgYWNyb3NzIEJvcnV0YSBwZXJtdXRhdGlvbnMsIGZyb20gNCBib290c3RyYXBzIGRyYXduIGF0IHJhbmRvbSBmcm9tIGVhY2ggb2YgdGhlIDUgcnVucyAoZ3JlZW4gPSBjb25maXJtZWQsIHJlZCA9IHJlamVjdGVkLCB5ZWxsb3cgPSB0ZW50YXRpdmUsIGJsdWUgbGluZXMgPSBzaGFkb3cgZmVhdHVyZSBtYXgsIG1lYW4sIGFuZCBtaW4pLl0oZmVhdGhpc3RfY29tcG9zaXRlXzVhbGdvLmpwZykKCiMjIE92ZXJsYXAgb2YgQ29uZmlybWVkIEZlYXR1cmVzCgpXZSBhbHNvIHN1bW1hcml6ZWQgdGhlIG92ZXJsYXAgaW4gY29uZmlybWVkIGFuZCByZWN1cnJlbnQgY29uZmlybWVkIGZlYXR1cmVzIGFjcm9zcyBib290c3RyYXAgcnVucy4gVGhlIGZvbGxvd2luZyB1cHNldCBwbG90cyBzaG93IHN1YnNldCBvdmVybGFwIG1lbWJlcnNoaXAgZm9yIGZlYXR1cmVzIGNvbmZpcm1lZCBhdCBsZWFzdCBvbmNlIGFjcm9zcyBib290c3RyYXBzLCBncmVhdGVyIHRoYXQgNSUgb2YgYm9vdHN0cmFwcywgb3IgZ3JlYXRlciB0aGFuIDIwJSBvZiBib290c3RyYXBzLgoKIVtGZWF0dXJlIG92ZXJsYXAgYW1vbmcgZmVhdHVyZXMgY29uZmlybWVkIGluIGF0IGxlYXN0IDEgYm9vdHN0cmFwLCBhY3Jvc3MgYm9vdHN0cmFwIHJ1bnMgd2l0aCA1IGltcG9ydGFuY2UgbWV0cmljcy5dKG5yYW5rLTRhbGdvX2djb25mYWxsX3Vwc2V0ci5qcGcpCgohW0ZlYXR1cmUgb3ZlcmxhcCBhbW9uZyBmZWF0dXJlcyBjb25maXJtZWQgaW4gYXQgbGVhc3QgNSUgb2YgYm9vdHN0cmFwIHJ1bnMsIGFjcm9zcyBib290c3RyYXAgcnVucyB3aXRoIDUgaW1wb3J0YW5jZSBtZXRyaWNzXShucmFuay00YWxnb19nY29uZjVwZXJjX3Vwc2V0ci5qcGcpCgohW0ZlYXR1cmUgb3ZlcmxhcCBhbW9uZyBmZWF0dXJlcyBjb25maXJtZWQgaW4gYXQgbGVhc3QgMjAlIG9mIGJvb3RzdHJhcCBydW5zLCBhY3Jvc3MgYm9vdHN0cmFwIHJ1bnMgd2l0aCA1IGltcG9ydGFuY2UgbWV0cmljc10obnJhbmstNGFsZ29fZ2NvbmYyMHBlcmNfdXBzZXRyLmpwZykKCg==